#define MAX_QUEUE_SIZE 100
#define ERROR 2
#define OK 1
typedef int ElemType;
typedef int Status;

typedef struct qnode
{
	ElemType data;
	struct qnode *next;
}QNode;

typedef struct linkqueue
{
	QNode *front,*rear;
}LinkQueue;

/*
	1.队列为空，front和rear同时指向头结点
	2.入队尾插法
	3.出队在链表头部出去

	也可以 带尾指针的循环单链表
	
	存储结构使链表
	链表没有存满一说，除非电脑内存全被使用了

	判断为空即 front == rear

	front总是指向头结点，front的next为队首
*/

//初始化
LinkQueue *Init_LinkQueue(void)
{
	LinkQueue *Q;
	QNode *p;
	p = (QNode *)malloc(sizeof(QNode));//开辟头结点
	p -> next = NULL;
	Q = (LinkQueue *)malloc(sizeof(QNode));
	/*开辟链队的指针结点*/
	Q.front = Q.rear = p;//队列的头和尾指向头结点

	return Q;
}

/*
	入队，队尾插入一个元素e
*/
Status Insert_LinkQueue(LinkQueue *Q,ElemType e)
{	
	QNode *p;
	p = (QNode *)malloc(sizeof(QNode));
	if (!p)
		return ERROR;//申请失败
	P -> data = e;
	p -> next = NULL;
	Q.rear -> next = p;
	Q.rear = p;//尾部指针始终指向最后一个

	return OK;
}

/*
	出队
*/
Status Delete_LinkQueue(LinkQueue *Q, ElemType *e)
{
	QNode *p;
	if (Q.front == Q,rear)
		return ERROR;//为空不能删除

	p = Q.front -> next;
	*e = p->data;
	Q.front -> next = p -> next;//队列头部的更换

	if (p == Q.rear)
		Q.rear = Q.front;//要删除的是最后一个将rear指向头
	//不修改指向删除会成为野指针

	free(p);

	return OK;
}

/*
	队列的撤销，将所有的结点出队，free
*/
void Destroy_LinkQueue(LinkQueue *Q)
{
	while (Q.front!=NULL)
	{
		Q.rear = Q.front -> next;
		//尾指针指向队列第一个结点
		free(Q.front);
		//每次释放一个节点，开始是头结点,之后是元素结点
		Q.front = Q.rear;
	}
}